package com.lz.sort;

/**
 * HeapSort..
 *
 * @author Lizhong
 * @date 2019/9/2
 */
public class HeapSort {
    /**
     *   完全二叉树
     *
     *   索引值为n的左结点索引值为2*n+1，右结点索引值为2*n+2;
     * - 索引值为n的父节点索引值为(n-1)/2，这里的“/”是整型变量相除得到的结果也是整型变量(学计算机的都懂^_^)。
     * - 结点数为size的完全二叉树非叶子结点数目为size/2，所以最后的那个非叶子结点的索引应该为(size/2)-1（因为从0开始，所以要减一）
     * - 结点数为size的完全二叉树叶子结点数目为size/2或size/2+1，这个结论在具体实现的时候用不到
     * @param items
     */
    public  void sort(int[] items) {
        // 构造二叉堆，从索引为0节点开始
        for (int i = items.length / 2 - 1; i >= 0; i--) {
            adjust(items, i, items.length);
        }

        for (int i = items.length - 1; i > 0; i--) {
            // 将最大值与最后项进行交换
            int temp = items[0];
            items[0] = items[i];
            items[i] = temp;

            // 取出最大值之后，重新调整二叉堆
            // 二叉堆也随着变量i慢慢缩小
            adjust(items, 0, i);
        }
    }

    /**
     * 比较左右节点，记录索引，索引变化交换值，若果是非叶子节点
     * @param items
     * @param index 非叶子节点索引
     * @param heapSize 元素个数
     */
    public  void adjust(int[] items, int index, int heapSize) {
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;

        // 在三个结点中选出最大的结点
        int indexOfMax = index;

       if (leftChild < heapSize) {// 左子树存在性检验
            if (items[leftChild] > items[indexOfMax]) {
                indexOfMax = leftChild;
            }
        }
        if (rightChild < heapSize) {// 右子树存在性检验
            if (items[rightChild] > items[indexOfMax]) {
                indexOfMax = rightChild;
            }
        }

        if (indexOfMax != index) {
            // 将较大值上移
            int temp = items[index];
            items[index] = items[indexOfMax];
            items[indexOfMax] = temp;

            // 千万别漏了这个等号，我调试了半天才发现这个错误
            // 找到最后一个飞叶子节点
            if (indexOfMax <= heapSize / 2 - 1) {
                adjust(items, indexOfMax, heapSize);
            }
        }

    }

    public static void main(String[] args) {
        int[] a = {12, 20, 5, 16, 15, 1, 30, 45, 5, 23, 9};
        HeapSort heapSort = new HeapSort();
        heapSort.sort(a);
        PrintUtil.printArray(a);
    }
}
